package one.lru;

import java.util.HashMap;
import java.util.Map;
/**
 LRU缓存机制
 时间复杂度：O(1)的访问；O(1)的更新；O(1)的删除
 思路：哈希表+双向链表
 双向链表：按时间顺序保存数据
 哈希表：把key映射到链表的节点（为了O(1)的访问）
 */
public class LRUCache {

    private int capacity;
    private Node head; //双链表的保护节点
    private Node tail; //双链表的保护节点
    private Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        //带有保护节点的空的双向链表
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }else{
            //获得并返回值
            Node node = map.get(key);
            //删除双向链表和Map中的node
            removeFromListMap(node);
            //在双向链表的头部插入node，并记录在Map中
            insertIntoListMap(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        if(!map.containsKey(key)){//插入
            Node node = new Node(key, value);
            insertIntoListMap(node);
        }else{//更新
            //删除双向链表和Map中的node
            Node node = map.get(key);
            removeFromListMap(node);
            //在双向链表的头部插入node，并记录在Map中
            node.value = value;
            insertIntoListMap(node);
        }
        if(map.size() > this.capacity){
            removeFromListMap(tail.pre);
        }
    }

    private void removeFromListMap(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        map.remove(node.key);
    }
    private void insertIntoListMap(Node node){
        //node和下一个节点建立连接
        node.next = head.next;
        head.next.pre = node;
        //node和head建立连接
        head.next = node;
        node.pre = head;
        //建立映射关系
        map.put(node.key, node);
    }

    //test
    public static void main(String[] args) {
        Node node = new Node(1, 2);
        System.out.println(node.key + " : " + node.value);
        node.value = 3;
        System.out.println(node.key + " : " + node.value);

    }
}
class Node{
    int key;
    int value;
    Node pre;
    Node next;
    public Node(){}
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}